package com.base.string;

import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.IntStream;

/**
 * 748. 最短补全词
 *
 * @author leon
 * @date 2021年12月10日 12:52
 */
public class ShortestCompletingWord {

    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] licence = toLowerAndToArray(licensePlate);
        String res = "";
        for (int i = 0; i < words.length; i++) {
            int[] word = toLowerAndToArray(words[i]);
            if(isArrayInOtherArray(licence,word)){
                if(res.length()==0){
                    res = words[i];
                }else {
                    res = res.length()>words[i].length()?words[i]:res;
                }
            }
        }

        return res;
    }

    private int[] toLowerAndToArray(String s){
        // 不区分大小写
        String ss = s.toLowerCase();
        int[] res = new int[26];

        for (int i = 0; i < ss.length(); i++) {
            char cur = ss.charAt(i);
            // 忽略数字与空格
            if(cur-'a'>=0&&cur-'z'<=0){
                res[cur-'a']++;
            }
        }
        return res;
    }

    private boolean isArrayInOtherArray(int[] a,int[] b){
        if(a.length != b.length){
            return false;
        }

        for (int i = 0; i < a.length; i++) {
            // 如果某个字母在 licensePlate 中出现不止一次，那么该字母在补全词中的出现次数应当一致或者更多。
            if(a[i]>b[i]){
                return false;
            }
        }
        return true;
    }
    // Java流写法
    public String shortestCompletingWord1(String licensePlate, String[] words) {
        String license = licensePlate.toLowerCase();
        short[] chars = new short[26];
        license.chars().filter(c->c>='a' && c <= 'z').forEach(c ->chars[c - 'a'] ++);
        return Arrays.stream(words).filter(word->{
            short[] wordChars = new short[26];
            word.chars().filter(c->c>='a' && c <= 'z').forEach(c->wordChars[c-'a'] ++);
            return IntStream.range(0,26).allMatch(i->wordChars[i] >= chars[i]);
        }).sorted(Comparator.comparingInt(String::length)).findFirst().get();
    }
    public static void main(String[] args) {
        System.out.println(new ShortestCompletingWord().shortestCompletingWord("1s3 PSt",new String[]{"step","","stripe","stepple","steps"}));
    }
}
